package net.cyndeline.scalarlib.rlgraph.util

import scalax.collection.immutable.Graph
import net.cyndeline.scalarlib.rlgraph.embedding.{AdjacencyEntry, Vertex, Embedding}
import net.cyndeline.scalarlib.rlgraph.face.Face
import scala.reflect.runtime.universe.TypeTag
import scalax.collection.GraphEdge.UnDiEdge
import scala.collection.mutable.ArrayBuffer
import scalax.collection.GraphPredef._

/**
 * Common operations performed on the graph-related data structures.
 */
object GraphCommons {

  /**
   * Computes neighbors of a node in a graph in O(n) time, where n = # of neighbors. Uses edges rather than the neighbor
   * method, since it returns nodes in random order when instantiating the same graph multiple times.
   * @param vertex Vertex to retrieve neighbors for.
   * @param graph Graph containing vertex.
   * @tparam VType Vertex type of graph.
   * @tparam EType Edge type of graph.
   * @return A list of vertices neighboring the input vertex, or an empty list if no neighbors exist.
   */
  def neighbors[VType, EType[X] <: EdgeLikeIn[X]](vertex: VType, graph: Graph[VType, EType]): Vector[graph.NodeT] = {
    graph.get(vertex).edges.map(e => if (e._1 == vertex) e._2 else e._1).toVector
  }

  /**
   * Computes the same neighbor set as neighbors(...), but casts the vertex list to their outer objects.
   * @param vertex Vertex to retrieve neighbors for.
   * @param graph Graph containing vertex.
   * @tparam VType Vertex type of graph.
   * @tparam EType Edge type of graph.
   * @return A list of vertices neighboring the input vertex, or an empty list if no neighbors exist.
   */
  def outerNeighbors[VType, EType[X] <: EdgeLikeIn[X]](vertex: VType, graph: Graph[VType, EType]): Vector[VType] = {
    val l = neighbors(vertex, graph)
    for {
      n <- l
      outer: VType = n
    } yield outer
  }

  /**
   * Finds the vertex opposite to a vertex in a graph.
   * @param vertex Vertex to find opposite neighbor of.
   * @param edge Edge that the input vertex is a member of.
   * @tparam VType Vertex type.
   * @tparam EType Edge type.
   * @return The vertex on the opposite end of the input edge.
   */
  def oppositeVertex[VType, EType[X] <: EdgeLikeIn[X]](vertex: VType, edge: EType[VType]): VType = {
    if (edge._1 == vertex) edge._2
    else if (edge._2 == vertex) edge._1
    else throw new Error("The edge " + edge + " did not contain " + vertex + ", cannot retrieve opposite vertex.")
  }

  /**
   * Splits a list and reconnects it such that the first entry of a specified element ends up as the head of the list.
   * @param e Element to place at the head of the list.
   * @param list List containing the vertex.
   * @tparam E Element type.
   * @return A list with all elements maintaining the same cyclical order as the input, but with the specified
   *         vertex as head.
   */
  def placeElementFirst[E](e: E, list: Vector[E]): Vector[E] = {
    val span: (Vector[E], Vector[E]) = list.span(_ != e)
    span._2 ++ span._1
  }

  /**
   * Embeds an edge inside a face in a planar embedding.
   * @param embedding Embedding of a planar graph.
   * @param face A face computed from the embedding.
   * @param a A vertex to add the new edge to in the embedding.
   * @param b A vertex opposite from 'a that should be connected using the new edge.
   * @return The embedding, containing a new edge from a to b.
   */
  def embedEdgeInFace[VType](embedding: Embedding[VType], face: Face[VType], a: VType, b: VType): Embedding[VType] = {
    val aInsertPos = face.edges.find(_._1 == a).get._2
    val bInsertPos = face.edges.find(_._1 == b).get._2
    embedding.embedEdge(Vertex(a) withInsertPosition bInsertPos inVertex b withInsertPosition aInsertPos)
  }

  /**
   * Splits the disconnected components of a graph into subgraphs.
   * @param graph The graph to compute connected components from.
   * @tparam VType Vertex type in the graph.
   * @tparam EType Edge type in the graph.
   * @return A list of every connected component in the graph. Contains only a single element if the initial graph
   *         was already connected.
   */
  def allConnectedComponents[VType : TypeTag, EType[X] <: EdgeLikeIn[X] : ({type l[M[_]] = TypeTag[M[VType]]})#l](graph: Graph[VType, EType]): Vector[Graph[VType, EType]] = {
    val components = graph.componentTraverser()
    val allGraphs = for (disconnectedComponent <- components.toVector) yield {
      val ee = disconnectedComponent.edges.toVector.map(_.toOuter)
      val nn = disconnectedComponent.nodes.toVector.map(n => { val outer: VType = n; outer })
      Graph.from(nn, ee)
    }

    allGraphs
  }

  /**
   * Converts the embedding into an undirected graph.
   *
   * @param embedding An embedding to convert into a graph.
   * @return A graph containing all vertices in the embedding, with edges constructed by the factory according to
   *         the embedded edge entries.
   */
  def embeddingAsGraph[VType : TypeTag](embedding: Embedding[VType]): Graph[VType, UnDiEdge] = {
    val edges = new ArrayBuffer[UnDiEdge[VType]]()
    val vertices = embedding.embeddedVertices.iterator

    while (vertices.hasNext) {
      val vertex = vertices.next()
      val adjacencyEntries: Iterator[AdjacencyEntry[VType]] = embedding.embeddingFor(vertex).iterator

      while (adjacencyEntries.hasNext) {
        val entry = adjacencyEntries.next()
        edges += vertex~entry.adjacentVertex
      }
    }

    Graph.from(embedding.embeddedVertices, edges.toVector)
  }

}
